package algorithms.sort.nlogn;

import algorithms.sort.SortingVisualization;

/**
 * 快速排序
 */
public class QuickSort extends SortingVisualization {

    /**
     * 初始化窗口大小并
     *
     * @param array
     */
    public QuickSort(int[] array) {
        super(array);
    }

    @Override
    public void showSortingProcess() {
        quickSort(array, 0, array.length - 1);
    }

    public void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            quickSort(array, low, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, high);
        }
    }

    public int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                i++;
                swap(array, i, j);
            }
        }

        swap(array, i + 1, high);

        return i + 1;
    }

    public void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        sortPanelRepaint();
    }
}
